package com.swak.algs;

/**
 * 插入排序： 相邻位置的两两交换
 * 
 * @author lifeng
 */
public class Code04 {

	static void print(int arr[]) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	static void swap(int arr[], int i, int n) {
		int temp = arr[i];
		arr[i] = arr[n];
		arr[n] = temp;
	}

	/**
	 * 标准的流程
	 * 
	 * @param arr
	 */
	public static void insertSort(int arr[]) {

		/*
		 * 边界的判断
		 */
		if (arr == null || arr.length < 2) {
			return;
		}

		/*
		 * 找到长度
		 */
		int N = arr.length;

		/*
		 * 0  ~  0     位置有序， 已经有序
		 * 0  ~  1     位置有序
		 * 0  ~  2      位置有序
		 * 0  ~  N-1 位置有序
		 * 注意这里的变化部分是结尾的数
		 */
		for (int end = 1; end <= N - 1; end++) {

			/*
			 * 为啥从1开始, 已经有序
			 */
			for (int j = end; j > 0; j--) {
				if (arr[j] > arr[j - 1]) {
					break;
				}
				swap(arr, j, j - 1);
			}
		}
	}

	public static void main(String[] args) {
		int arr[] = { 1, 4, 2, 6, 8, 9, 5 };
		print(arr);
		insertSort(arr);
		print(arr);
	}
}
